﻿#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class MaxSubArray {
public:
	vector<int> findMaxSubArray(vector<int>& original_array)
	{
		vector<int> Array(original_array);
		vector<int> param = findMaxVal(Array, 0, Array.size()-1);
		vector<int> result;
		for (int i = 0; i < Array.size(); i++)
		{
			if (param[1] <= i && i <= param[2])
			{
				result.push_back(Array[i]);
			}
		}
		return result;
	}
	vector<int> findMaxVal(vector<int>& array, int l, int r)
	{
		if (l == r)
		{
			vector<int> param;
			param.push_back(array[l]);
			param.push_back(l);
			param.push_back(r);
			return param;
		}
		int mid = (l + r) / 2;
		vector<int> paraml = findMaxVal(array, l, mid);
		vector<int> paramr = findMaxVal(array, mid+1, r);
		vector<int> accl, accr;
		int acclnum=0, accrnum=0;
		for (int i = mid; i >= l; i--)
		{
			acclnum += array[i];
			accl.push_back(acclnum);
		}
		for (int i = mid; i <=r ; i++)
		{
			accrnum += array[i];
			accr.push_back(accrnum);
		}
		vector<int>::iterator maxl = max_element(begin(accl), end(accl));
		vector<int>::iterator maxr = max_element(begin(accr), end(accr));
		int midl = mid - distance(begin(accl), maxl);
		int midr = mid + distance(begin(accr), maxr);
		int midmax = *maxl + *maxr-array[mid];
		if (midmax > paraml[0] && midmax > paramr[0])
		{
			vector<int> param;
			param.push_back(midmax);
			param.push_back(midl);
			param.push_back(midr);
			return param;
		}
		else if (paraml[0] > paramr[0] && paraml[0] > midmax)
		{
			return paraml;
		}
		else
		{
			return paramr;
		}
	}
};
vector<int> subArray_foolmethod(vector<int> &array)
{
	vector<int> l;
	vector<int> r;
	vector<int> num;
	for (int i = 0; i < array.size(); i++)
	{
		for (int j = i; j < array.size(); j++)
		{
			l.push_back(i);
			r.push_back(j);
			int acc = 0;
			for (int n = i; n <= j; n++)
			{
				acc += array[n];
			}
			num.push_back(acc);
		}
	}
	vector<int>::iterator max = max_element(num.begin(), num.end());
	int indix = distance(begin(num), max);
	vector<int> subarray;
	for (int i = l[indix]; i <= r[indix]; i++)
	{
		subarray.push_back(array[i]);
	}
	return subarray;
}


int main()
{
	vector<int> testseque = { -1,6,5,4,3,-9,-7,15,-3,6,9,-10,5,44,8,-9,35,5,-7 };
	MaxSubArray obj;
	vector<int> subarray = obj.findMaxSubArray(testseque);
	for (int i = 0; i < subarray.size(); i++)
	{
		cout << subarray[i] << '\t';
	}
	cout << endl;
	vector<int>subarray2 = subArray_foolmethod(testseque);
	for (int i = 0; i < subarray2.size(); i++)
	{
		cout << subarray2[i] << '\t';
	}
}
